
// 23.合并K个升序链表
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    // 两两一合并
    ListNode* _Merge_Base(ListNode* l1 , ListNode* l2)
    {
        ListNode* phead = new ListNode , *tail = phead;
        ListNode *cur1 = l1 , *cur2 = l2;
        while(cur1 || cur2)
        {
            if(cur1 && (cur2 == nullptr || cur1->val < cur2->val)) 
            {
                tail->next = cur1;
                cur1 = cur1->next;
                tail = tail->next;
            }
            else 
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }
        ListNode* ret = phead->next;
        tail->next = nullptr;
        delete phead;
        return ret;
    }        
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if(n == 0) return nullptr;
        ListNode* ret = lists[0];
        for(int i = 1 ; i < n ; i++)
            ret = _Merge_Base(ret , lists[i]);

        return ret;
    }
};